from typing import List


class Solution:
    """
    方法：合并重叠区间
    1. 首先将所有区间按照左端点进行排序
    2. 遍历排序后的区间列表，逐个检查是否可以与结果列表中的最后一个区间合并
    3. 如果可以合并，则更新最后一个区间的右端点
    4. 如果不能合并，则将该区间加入结果列表

    Args:
        intervals: List[List[int]] - 包含多个区间的列表，每个区间表示为[start, end]

    Returns:
        List[List[int]] - 合并后的区间列表

    Time: O(nlogn) - 排序需要O(nlogn)，遍历需要O(n)
    Space: O(n) - 需要存储结果列表
    """
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        intervals.sort(key=lambda p:p[0]) # 按照左端点从小到大排序
        ans = []
        for p in intervals:
            if ans and p[0] <= ans[-1][1]: # 可以合并
                ans[-1][1] = max(ans[-1][1], p[1])
            else:
                ans.append(p)
        return ans